#include <vector>
#include <iostream>

using namespace std;

// 
class Solution0 {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();

        vector<vector<int>> dp(m + 1, vector<int>(n + 2));
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j + 1])) + matrix[i - 1][j - 1];
                if (j == 1)
                    dp[i][0] = dp[i][1];
                if (j == m)
                    dp[i][m + 1] = dp[i][m];
            }
        }

        int Min = dp[m][1];
        for (int i = 1; i <= n; i++)
        {
            Min = min(Min, dp[m][i]);
        }
        return Min;
    }
};



//
class Solution1 {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        dp[0][1] = dp[1][0] = 0;

        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }

        return dp[m][n];
    }
};


//
//class Solution {
//public:
//    int calculateMinimumHP(vector<vector<int>>& dungeon) {
//        int m = dungeon.size(), n = dungeon[0].size();
//        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
//        dp[0][1] = dp[1][0] = 1;
//
//        for (int i = 1; i <= m; i++)
//        {
//            for (int j = 1; j <= n; j++)
//            {
//                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) - dungeon[i - 1][j - 1];
//                if (dp[i][j] <= 0)
//                    dp[i][j] = 1;
//            }
//        }
//
//        return dp[m][n];
//    }
//};

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size(), n = dungeon[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        dp[m][n - 1] = dp[m - 1][n] = 1;
        for (int i = m - 1; i >= 0; i--)
        {
            for (int j = n - 1; j >= 0; j--)
            {
                dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                if (dp[i][j] <= 0)
                    dp[i][j] = 1;
            }
        }

        return dp[0][0];
    }
};

int main()
{
    vector<vector<int>> dungeon({ {-2, -3, 3},{-5, -10, 1}, {10, 30, -5} });

    cout << Solution().calculateMinimumHP(dungeon) << endl;
    return 0;
}